package com.ocean.divideandconquer.easy;

/**
 * <Description> <br>
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/24 <br>
 */
public class MergeSortCounting {

    private int num = 0; // 全局变量或者成员变量

    public int count(int[] a, int n) {
        num = 0;
        mergeSortCounting(a, 0, n - 1);
        return num;
    }

    private void mergeSortCounting(int[] a, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = (start + end) / 2;
        mergeSortCounting(a, start, mid);
        mergeSortCounting(a, mid + 1, end);
        merge(a, start, mid, end);
    }

    private void merge(int[] a, int start, int mid, int end) {
        int i = start, j = mid + 1, k = 0;
        int[] tmp = new int[end - start + 1];
        while (i <= mid && j <= end) {
            if (a[i] <= a[j]) {
                tmp[k++] = a[i++];
            } else {
                num += (mid - i + 1); // 统计p-q之间，比a[j]大的元素个数
                tmp[k++] = a[j++];
            }
        }
        while (i <= mid) { // 处理剩下的
            tmp[k++] = a[i++];
        }
        while (j <= end) { // 处理剩下的
            tmp[k++] = a[j++];
        }
        for (i = 0; i <= end - start; ++i) { // 从tmp拷贝回a
            a[start + i] = tmp[i];
        }
    }
}
